package ljl.alg.wangzheng_camp.round1.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * 网上这种搓比方法，居然不慢！
 * */
public class _17_14_smallest_k {
    
    public int[] smallestK(int[] arr, int k) {
        quickSelect(arr, 0, arr.length - 1, k);
        return Arrays.copyOf(arr, k);
    }
    
    void quickSelect(int[] arr, int from, int to, int k) {
        if (from >= to) return;
        int i = par(arr, from, to);
        if (i == k - 1) return;
        if (i > k - 1) quickSelect(arr, from, i - 1, k);
        else quickSelect(arr, i + 1, to, k);
    }
    
    int par(int[] arr, int from, int to) {
        int l = from - 1;
        int t = arr[to];
        for (int i = from; i < to; i++) {
            if (arr[i] <= t) swap(arr, ++l, i);
        }
        swap(arr, ++l, to);
        return l;
    }
    
    void swap(int[] arr, int l, int r) {
        if (l != r) {
            int t = arr[l]; arr[l] = arr[r]; arr[r] = t;
        }
    }
    
    /*
    * 快选再写一遍吧，还是不太熟
    *
    * 居然写错辣我不服
    * 下面那个 arr[l] = arr[r] 写成 = t 了，小问题
    *
    * */
    class mine_mine {
        public int[] smallestK(int[] arr, int k) {
            quickSelect(arr, 0, arr.length - 1, k);
            return Arrays.copyOf(arr, k);
        }
        Random rdm = new Random();
        void quickSelect(int[] arr, int from, int to, int k) {
            if (from >= to) return;
            int l = from, r = to;
            int idx = from + rdm.nextInt(to - from + 1);
            swap(arr, from, idx);
            int t = arr[l];
            while (l < r) {
                while (l < r && arr[r] >= t) r--;
                arr[l] = arr[r];
                while (l < r && arr[l] <= t) l++;
                arr[r] = arr[l];
            }
            arr[l] = t;
            if (l == k - 1) return;
            if (l > k - 1) quickSelect(arr, from, l - 1, k);
            else quickSelect(arr, l + 1, to, k);
        }
        
    }
    
    /*
    * 现在市面上流行的写法，先放这，我当然是得改改了
    * */
    class often_used {
        
        public int[] smallestK(int[] arr, int k) {
            randomizedSelected(arr, 0, arr.length - 1, k);
            int[] vec = new int[k];
            for (int i = 0; i < k; ++i) {
                vec[i] = arr[i];
            }
            return vec;
        }
    
        private void randomizedSelected(int[] arr, int l, int r, int k) {
            if (l >= r) {
                return;
            }
            int pos = randomizedPartition(arr, l, r);
            int num = pos - l + 1;
            if (k == num) {
            } else if (k < num) {
                randomizedSelected(arr, l, pos - 1, k);
            } else {
                randomizedSelected(arr, pos + 1, r, k - num);
            }
        }
    
        private int randomizedPartition(int[] nums, int l, int r) {
            int i = new Random().nextInt(r - l + 1) + l;
            swap(nums, r, i);
            return partition(nums, l, r);
        }
    
        private int partition(int[] nums, int l, int r) {
            int pivot = nums[r];
            int i = l - 1;
            for (int j = l; j <= r - 1; ++j) {
                if (nums[j] <= pivot) {
                    i = i + 1;
                    swap(nums, i, j);
                }
            }
            swap(nums, i + 1, r);
            return i + 1;
        }
    
    }
    
}
